/**
 * @autor my
 * 2017/8/15.
 */
public class ElectKing {
    /*所有猴子按 1，2 ……… n 编号并按照顺序围成一圈，从第 k 个猴子起，由1开始报数，报到m时，该猴子就跳出圈外，
    下一只猴子再次由1开始报数，如此循环，直到圈内剩下一只猴子时，这只猴子就是大王。*/
    public static int[] elect(int[] num,int start,int count){
        /*num长度为猴子数量，start为开始报数的猴子，从一开始报数，报到end时，该猴子跳出圈外
        该方法为一遍报数*/
        /*out为要出去的猴子*/
        int out;
        /*因为start可能大于num的长度，所以out=（start+count-1-1）%num.length-1+1*/
        if ((start+count-1)%num.length==0){
            out=(start+count-2)%num.length;
        }
        else {
            out =(start+count-1)%num.length - 1;
        }
        /*新建一个数组newMun，用于存储剩下的猴子*/
            int[] newNum = new int[num.length - 1];
        /*把剩下的猴子填入新的数组*/
            for (int i = 0; i < num.length; i++) {
                if (i<out){
                    newNum[i]=num[i];
                    break;
                }
                else if (i==out){
                    break;
                }
                else{
                    newNum[i-1]=num[i];
                    break;
                }
            }
            return newNum;
    }
    public static int king(int[] num,int start,int count){
        /*用递归重复报数过程，直到只剩最后一只猴子，这个猴子就是大王，
        也就是newMun数组里只剩一个元素，这个元素存的数就是大王的位置*/
        int[] newNum=elect(num,start,count);
        while (newNum.length>1){
            /*如果start猴子报数到了最后一个，下一次就从第一个猴子开始*/
            start=(start+1)%newNum.length;
            if (start==0){
                start=start%newNum.length+1;
                king(newNum,start,count);
            }
            else {
                king(newNum, start, count);
            }
        }
        int result=newNum[0];
            return result;
    }
    public static void main(String[] args) {
        /*简单测试下*/
        int[] a={1,2,3,4,5,6};
        int king=king(a,1,3);
        System.out.println("大王就是我："+king+"号！！！");
    }
}
